RMQ在线 && 二维离线

CF1887D

题意：

定义一个数组是好的，仅当其可分割成两个非空数组，使得左边元素都小于右边元素

即满足 max(al…ak) ≤ min(ak + 1…ar)

给定排列，q次查询，问 [l, r] 的子数组是否是好的

(n, q ≤ 3e5)

 

解析：

固定 l，r，若枚举 k，左右两侧都是单增，因此整体不存在单调性

 

法 1：

二维离线

 

从值考虑

我们考虑左侧区间中的最大值，

若 ai 成为最大值，我们记 i 左侧第一个大于 ai 的元素位置为 l1，则有限制 l1 < L ≤ i

我们记 i 右侧第一个大于 ai 的元素位置为 r1，记 r1 右侧第一个小于 ai 的元素位置为 r2，则有限制 r1 ≤ R < r2

这样的 [L, R] 就是左侧以 ai 为最大值的好区间

( i 左右找  > ai 的第一个位置是很典的问题，可以用单调队列，笛卡尔树，按值枚举甚至还可以用 set )

 

也就是，以 ai 为最大的合法情况落在矩阵 L ∈ [l1 + 1, i], R ∈ [r1, r2 − 1] 上

 

我们维护合法情况，离线所有查询，以 r 升序

从左向右枚举 i

当遍历到 r1 时，我们对 [l1 + 1, i] 区间+1，遍历到 r2 时，对 [l1 + 1, i] 区间-1，正值则代表该点合法

然后对 R=i 的查询， L 是否合法即可

 

trick：

在此过程中，我们需要 区间加&单点查

实现上可使用树状数组维护差分

区间加相当于在差分数组上单点修改，对某点的查询相当于差分数组的前缀和

(当然直接用线段树也是可以的喵)

 

时间复杂度 O(n + q)log

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct BIT{
    int n;
    vector<ll> tree;
    BIT(int _n) : n(_n){
        tree.resize(n + 1);
    }

    void add(int x, ll v){
        for(int i=x; i<=n; i+=i&-i){
            tree[i] += v;
        }
    }

    ll query(int x){
        ll ans = 0;
        for(int i=x; i>=1; i-=i&-i){
            ans += tree[i];
        }
        return ans;
    }
    ll query(int x, int y){
        return query(y) - query(x - 1);
    }

};

// 二维离线
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> idx(n + 1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        idx[a[i]] = i;
    }

    int q;
    cin >> q;
    vector<vector<pii>> qry(n + 1);
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        qry[r].push_back({l, i});
    }

    // 预处理 >ai 最近的位置，>R[i]&<ai的最近位置
    vector<int> L(n + 2), R(n + 2), Rle(n + 2);
    {
        set<int> st{0, n+1};
        for(int i=n; i>=1; i--){
            int p = idx[i];
            L[p] = *prev(st.lower_bound(p));
            R[p] = *st.lower_bound(p);
            st.insert(p);
        }
    }
    {
        set<int> st{0, n+1};
        for(int i=1; i<=n; i++){
            int p = idx[i];
            Rle[p] = *st.lower_bound(R[p]);
            st.insert(p);
        }
    }

    // r1 -> [l1, i]  r2 -> [l1, i]
    vector<vector<pii>> add(n + 2), del(n + 2);
    for(int i=1; i<=n; i++){
        int r1 = R[i];
        int r2 = Rle[i];
        if(L[i]+1<=i && r1 < r2){
            // debug(L[i]+1, i, r1, r2)
            add[r1].push_back({L[i], i});
            del[r2].push_back({L[i], i});
        }
    }
    
    vector<bool> ans(q + 1);
    BIT bit(n+1);
    for(int i=1; i<=n; i++){
        for(auto[l, i] : add[i]){
            bit.add(l+1, 1);
            bit.add(i+1, -1);
        }
        for(auto[l, i] : del[i]){
            bit.add(l+1, -1);
            bit.add(i+1, 1);
        }
        for(auto[L, i] : qry[i]){
            ans[i] = (bit.query(L)>0);
        }
    }

    for(int i=1; i<=q; i++){
        cout << (ans[i]? "Yes":"No") << '\n';
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1; // cin >> t;
    while(t--) solve();

    return 0;
}

 

法 2：

RMQ 在线查询 & 跳表求离散数组最值

 

这种想法比较直接

我们直接固定 l，从 l 向右建单调队列

显然，ax 能成为最大值，仅当 ax 在单调队列里存在

 

我们枚举 ax，令 r1 为第一个满足 ar1 > ax 位置，令 r2 为第一个满足 r2 > r1, ar2 < ax 的位置

则合法的 R ∈ [r1, r2 − 1]

 

只需要在所有 ax 中找最远的 R

在以 l 为左端点的询问中，r ≤ R 即为 “Yes”

 

现在考虑如何快速的在离散的 ax 中找到最大 R

 

可以使用 st 表

若是连续区间，对两个长度为 2k − 1 区间求 max 即可

但离散的 ax 就不能这样了

 

我们需要先处理出从 x 后第 2k − 1 个元素的下标，也就是 nxt 表 (st表)

然后就能求离散数组的 max 了

具体实现参考代码

 

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MX = 3e5;
vector<int> LOG(MX + 1);
void init(){
    for(int i=2; i<=MX; i++){
        LOG[i] = LOG[i>>1] + 1;
    }
}

// 在线RMQ & 跳表 & 离散数组最值
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> idx(n + 1);
    for(int i=1; i<=n; i++){
        cin >> a[i];
        idx[a[i]] = i;
    }

    // 处理 >ai 最近的位置，>R[i]&<ai的最近位置
    vector<int> R(n + 2), Rle(n + 2);
    {
        set<int> st{0, n+1};
        for(int i=n; i>=1; i--){
            int p = idx[i];
            R[p] = *st.lower_bound(p);
            st.insert(p);
        }
    }
    {
        set<int> st{0, n+1};
        for(int i=1; i<=n; i++){
            int p = idx[i];
            Rle[p] = *st.lower_bound(R[p]);
            st.insert(p);
        }
    }

    // i -> { ap1 ap2 ... }，nxt&mx(st表) 求离散数列最大值
    int m = LOG[n];
    vector<vector<int>> nxt(n + 2, vector<int>(m + 1)), mx = nxt;
    for(int i=1; i<=n; i++){
        nxt[i][0] = R[i];
        mx[i][0] = Rle[i]-1;
    }
    for(int k=1; k<=m; k++){
        for(int i=1; i<=n; i++){
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];
            mx[i][k] = max(mx[i][k-1], mx[nxt[i][k-1]][k-1]);
        }
    }
    // 查左端点 l，x <= r 的最大的 R
    auto get = [&](int l, int r){
        int R = 0, x = l;
        for(int k=m; k>=0; k--){
            if(nxt[x][k] && nxt[x][k] <= r){
                R = max(R, mx[x][k]);
                x = nxt[x][k];
            }
        }
        return R;
    };

    int q; cin>>q;
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        int R = get(l, r);
        cout << (r<=R? "Yes":"No") << '\n';
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

    int t = 1; // cin >> t;
    while(t--) solve();
    
    return 0;
}